oracle machine
oracle
#complexity_theory
#complexity_theory
Definition
An oracle machine be visualized as Turing machine with a black box (oracle), able to solve a certain kind of problem in a single operation.
Notes
- useful to study how certain operation complexities depend on other ones (without necessarily defining that operation's complexity)
- formalization: oracle Turing machine (which similarly allows non-deterministic oracle TM to be defined)
- see also: Baker-Gill-Solovay theorem
References:
- https://en.wikipedia.org/wiki/Oracle_machine
- S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, pp. 73-74.